//
// Created by dgy on 2022/10/1.
//
#include "iostream"
using namespace std;
struct ListNode{
    ListNode() {

    }

    int val;
    ListNode *next;
    ListNode(int x):val(x),next(NULL){}
};
ListNode* mergeTwoLists(ListNode *l1,ListNode *l2){
        ListNode *p,*q,*head,*s;
        head=new ListNode();
        s=head;
        p=l1,q=l2;
        if (p==NULL)
            return l2;
        if (q==NULL)
            return l1;
        if(p==NULL&&q==NULL)
            return l1;
        while (p!=NULL&&q!=NULL){
            if(p->val<=q->val){
                s->next=p;
                s=p;
                p=p->next;
            } else{
                s->next=q;
                s=q;
                q=q->next;
            }
        }
        if(p==NULL){
            while(q!=NULL){
                s->next=q;
                s=q;
                q=q->next;
            }
        }
        if(q==NULL){
            while(p!=NULL){
                s->next=p;
                s=p;
                p=p->next;
            }
        }
        return head->next;
}